// Buffer cache.
//
// The buffer cache is a linked list of buf structures holding
// cached copies of disk block contents.  Caching disk blocks
// in memory reduces the number of disk reads and also provides
// a synchronization point for disk blocks used by multiple processes.
//
// Interface:
// * To get a buffer for a particular disk block, call bread.
// * After changing buffer data, call bwrite to flush it to disk.
// * When done with the buffer, call brelse.
// * Do not use the buffer after calling brelse.
// * Only one process at a time can use a buffer,
//     so do not keep them longer than necessary.
//
// The implementation uses three state flags internally:
// * B_BUSY: the block has been returned from bread
//     and has not been passed back to brelse.
// * B_VALID: the buffer data has been initialized
//     with the associated disk block contents.
// * B_DIRTY: the buffer data has been modified
//     and needs to be written to disk.

#include "types.h"
#include "defs.h"
#include "param.h"
#include "spinlock.h"
#include "buf.h"

struct {
  struct spinlock lock;
  struct buf buf[NBUF];

  struct buf* atable[NBUF];
  // Linked list of all buffers, through prev/next.
  // head.next is most recently used.
  struct buf head;
} bcache;

uint hash(uint sec){
	return sec % NBUF;
}

int count_buffers(uint inum){
	struct buf* b;
	int count = 0;

	for(b = bcache.buf; b < bcache.buf+NBUF; b++){
		if(b->inode_num == inum)
			count++;
	}
	return count;
}

void print_bcache(){

	uint sec;
	uint dev;
	uint i_num;

	struct buf *b;
	cprintf("BC = [");
	  for(b = bcache.buf; b < bcache.buf+NBUF; b++){
		  sec = b->sector;
		  dev = b->dev;
		  i_num = b->inode_num;
		  if(b->dev != -1){
		  	if(i_num == 0)
				cprintf("<%d,K,K>, ", dev);
		  	else
			  	cprintf("<%d,%d,%d>, ", dev, sec, i_num);
		  }
	  }
	  cprintf("]\n");
}


void
binit(void)
{
  struct buf *b;

  initlock(&bcache.lock, "bcache");

  // Create linked list of buffers
  bcache.head.prev = &bcache.head;
  bcache.head.next = &bcache.head;
  for(b = bcache.buf; b < bcache.buf+NBUF; b++){
    b->next = bcache.head.next;
    b->prev = &bcache.head;
    b->anext = 0;
    b->aprev = 0;
    b->allocated = 0;
    b->dev = -1;
    bcache.head.next->prev = b;
    bcache.head.next = b;
    b->inode_num = 0;
  }
  int i;
  for(i = 0; i < NBUF; i++){
	  bcache.atable[i] = 0;
  }
}

int
remove(struct buf* b) {

  uint index;

  index = hash(b->sector);

//first and last
  if(b->anext == 0 && b->aprev == 0){
  	bcache.atable[index] = 0;
  }
//first and not last
  else if(b->anext != 0 && b->aprev == 0){
  	bcache.atable[index] = b->anext;
  	b->anext->aprev = 0;
  }
//last
  else if(b->anext == 0 && b->aprev != 0){
  	b->aprev->anext = b->anext;
  }
//not first and not last, in the middle
  else if(b->anext != 0 && b->aprev != 0){
  	b->anext->aprev = b->aprev;
  	b->aprev->anext = b->anext;
  }
  return 0;
}

// Look through buffer cache for sector on device dev.
// If not found, allocate fresh block.
// In either case, return locked buffer.
static struct buf*
bget(uint dev, uint sector, uint inum)
{
  struct buf *b, *anchor_b;

  acquire(&bcache.lock);
  uint index = hash(sector);

 loop:
  anchor_b = bcache.atable[index];
  // Try for cached block.
  for(b = anchor_b; b != 0; b = b->anext){
    if(b->dev == dev && b->sector == sector){
      if(!(b->flags & B_BUSY)){
        b->flags |= B_BUSY;
        release(&bcache.lock);
        return b;
      }
      cprintf("going to sleep bget\n");
      sleep(b, &bcache.lock);
      cprintf("wokeup in bget\n");
      goto loop;
    }
  }

  int replace_buffer = 0;
  if(SRP > 2 && count_buffers(inum) == SRP){
  	replace_buffer = 1;
	//cprintf("SRP > 2 and count_buffers equals to SRP\n");
  }

  // Allocate fresh block.
  for(b = bcache.head.prev; b != &bcache.head; b = b->prev){
    if(replace_buffer == 1){
    	if(b->inode_num != inum){
    		continue;
    	}
    }
    
    if((b->flags & B_BUSY) == 0){
    	b->dev = dev;
    	b->sector = sector;
    	b->flags = B_BUSY;

    	//remove
    	if(b->allocated != 0){
		remove(b);
  	}
  	anchor_b = bcache.atable[index];
  	bcache.atable[index] = b;
  	b->anext = anchor_b;
  	if(anchor_b != 0)
		anchor_b->aprev = b;
  	b->aprev = 0;
  	b->allocated = 1;
  	#ifdef TRUE
		print_bcache();
  	#endif
  	release(&bcache.lock);
  	return b;
    }
  }
  panic("bget: no buffers");
}

// Return a B_BUSY buf with the contents of the indicated disk sector.
struct buf*
bread(uint dev, uint sector, uint inum)
{
  struct buf *b;

  b = bget(dev, sector, inum);
  if(!(b->flags & B_VALID))
    iderw(b);
  return b;
}

// Write b's contents to disk.  Must be locked.
void
bwrite(struct buf *b)
{
  if((b->flags & B_BUSY) == 0)
    panic("bwrite");
  b->flags |= B_DIRTY;
  iderw(b);
}

// Release the buffer b.
void
brelse(struct buf *b)
{

  if((b->flags & B_BUSY) == 0)
    panic("brelse");

  acquire(&bcache.lock);

  b->next->prev = b->prev;
  b->prev->next = b->next;
  b->next = bcache.head.next;
  b->prev = &bcache.head;
  bcache.head.next->prev = b;
  bcache.head.next = b;

  b->flags &= ~B_BUSY;
  wakeup(b);

  release(&bcache.lock);
}

